#include <stdio.h>

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// 插入排序
void insertion_sort(int unsorted_array[], int num_elements) {
    for (int i = 1; i < num_elements; i++) {
        int key = unsorted_array[i];
        int j = i - 1;
        
        // 将大于key的元素移到前面
        while (j >= 0 && unsorted_array[j] > key) {
            unsorted_array[j + 1] = unsorted_array[j];
            j--;
        }
        unsorted_array[j + 1] = key;
        
        // 打印当前数组状态
        print_array(unsorted_array, num_elements);
    }
}

// 快速排序
int partition(int L[], int low, int high, int total_num_elements) {
    int pivot = L[low];
    int i = low + 1;
    for (int j = low + 1; j <= high; j++) {
        if (L[j] < pivot) {
            int temp = L[i];
            L[i] = L[j];
            L[j] = temp;
            i++;
        }
    }
    // 将 pivot 移到正确的位置
    L[low] = L[i - 1];
    L[i - 1] = pivot;
    
    // 打印当前数组状态
    print_array(L, total_num_elements);
    
    return i - 1;
}

void QSort(int L[], int low, int high, int total_num_elements) {
    if (low < high) {
        int pivot_index = partition(L, low, high, total_num_elements);
        QSort(L, low, pivot_index - 1, total_num_elements);
        QSort(L, pivot_index + 1, high, total_num_elements);
    }
}

// 堆排序
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        // 打印当前数组状态
        print_array(arr, n);

        heapify(arr, n, largest);
    }
}

void heap_sort(int unsorted_array[], int num_elements) {
    // 建立最大堆
    for (int i = num_elements / 2 - 1; i >= 0; i--)
        heapify(unsorted_array, num_elements, i);

    // 一个个提取元素
    for (int i = num_elements - 1; i >= 0; i--) {
        // 将当前根（最大值）放到数组的末尾
        int temp = unsorted_array[0];
        unsorted_array[0] = unsorted_array[i];
        unsorted_array[i] = temp;

        // 打印当前数组状态
        print_array(unsorted_array, num_elements);

        heapify(unsorted_array, i, 0);
    }
}

// 主函数
int main() {
    int array1[] = {4, 3, 2, 1};
    int size1 = sizeof(array1) / sizeof(array1[0]);
    printf("Insertion Sort:\n");
    insertion_sort(array1, size1);

    int array2[] = {3, 1, 2, 5, 4};
    int size2 = sizeof(array2) / sizeof(array2[0]);
    printf("\nQuick Sort:\n");
    QSort(array2, 0, size2 - 1, size2);
    
    int array3[] = {70, 60, 12, 40, 30, 8, 10};
    int size3 = sizeof(array3) / sizeof(array3[0]);
    printf("\nHeap Sort:\n");
    heap_sort(array3, size3);
    return 0;
}